#include<stdio.h>

int **M;//各作业所需的处理时间
int *x;//当前作业调度
int *bestx;//当前最优作业调度
int *f2;//机器二完成处理的实践
int f1;//机器一完成处理的时间
int f;//完成时间和
int bestf;//当前最优值
int n;//作业数


void DJDD_Backtrack(int i)
{
	if(i>n)
	{//到达叶子结点
		for(int j=1; j<=n; ++j)
			bestx[j]=x[j];
		bestf = f;
	}else
		for(int j=i; j<=n; ++j)  // 因为问题的解空间是一颗由x[1:n]的所有排列构成的排列树
		{ // 所以第i次所调度的作业是从序号为i到n的作业中选择一个座位子树分支
			f1 += M[x[j]][1]; // +第i次所调度的作业在机器1上的处理时间
			f2[i] = ((f2[i-1]>f1) ? f2[i-1] : f1) + M[x[j]][2];
			f += f2[i];      //  +第i次所调度的作业在机器2上的处理时间
			if(f<bestf)
			{
				Swap(x[i], x[j]);
				Backtrack(i+1);
				Swap(x[i], x[j]);
			}
			f1 -= M[x[j]][1]; // -第i次所调度的作业在机器1上的处理时间
			f -= f2[i];       // -第i次所调度的作业在机器2上的处理时间
		}
		
}


int n;//集装箱数量
int *x;//当前解, 标记数组 1为选择放入 0为没选择
int *bestx;//当前最优解
int *w; //集装箱重量数组
int c; //第一艘轮船的载重量
int cw;//当前载重量
int bestw;//当前最优载重量
int r;//剩余集装箱重量

void Backtrack(int i)
{//i,搜索第i层结点,初值为1
	if(i>n)
	{//到达叶子节点
		if(cw > bestw)//当前载重量大于当前最优载重量
		{
			for(int j = 1; j<=n; j++)
			{
				bestx[j] = x[j];
				bestw = cw;
				return;
			}
		}
	}

	r -= w[i];//

	if(cw + w[i] <= c)
	{//当前载重加上备选放入的箱子小于轮船的载重量
	 //搜索左子树

	 x[i] = 1;
	 cw += w[i];
	 Backtrack(i+1);
	 cw -= w[i];
	}
	if(cw + r > bestw)
	{//当前的重量加上剩余的集装箱重量大于当前最优解
	 //遍历右子树

	 x[i] = 0;
	 Backtrack(i+1);
	}

	r += w[i];//
}